The invention relates generally to the field of digital data networks and more particularly to systems and methods for facilitating determination by router nodes in a network of ranges of addresses for which each router node is responsible.
In modem xe2x80x9centerprisexe2x80x9d digital data processing systems, that is, computer systems for use in an office environment in a company, a number of devices, such as personal computers, workstations, and other devices such as mass storage subsystems, network printers and interfaces to the public telephony system, are typically interconnected in a computer network. The personal computers and workstations (generally, xe2x80x9ccomputersxe2x80x9d) are used by individual users to perform processing in connection with data and programs that may be stored in the network mass storage subsystems. In such an arrangement, the computers, operating as clients, access the data and programs from the network mass storage subsystems for processing. In addition, the computers will enable processed data to be uploaded to the network mass storage subsystems for storage, to a network printer for printing, to the telephony interface for transmission over the public telephony system, or the like. In such an arrangement, the network mass storage subsystems, network printers and telephony interface operate as servers, since they are available to service requests from all of the clients in the network. By organizing the network in such a manner, the servers are readily available for use by all of the computers on the network.
Typically in a network, information is transferred in the form of packets, which are transferred from source devices, over communication links and through switching or router nodes, to destination devices. Each device is identified by an address, and each message packet includes a destination address which identifies the address of the device that is to receive the message packet as the destination device. As each router node receives a message packet from either the source device or another router node along a path from the source device to the destination device, it (that is, the router node) determines from the destination address the particular communication link or links over which it should transfer the message packet either to the next router node along the path to the destination device, or to the destination device itself A group of devices connected in the network may also be identified by a so-called xe2x80x9cmulticastxe2x80x9d address, in which case a message packet containing the multicast address as the destination address will be transferred to all of the devices in the group, and, if a router node receives a message packet whose destination address is a multicast address, it (that is, the router node) may transmit the message packet over one or a plurality of communication links connected thereto. The router nodes and switches, and perhaps other components which transfer message packets among devices, are generally also identified by respective addresses, and perhaps may be included in multicast groups, so as to facilitate transfer of message packets thereto. Typically, the addresses of individual devices and other components, which will also be referred to herein as xe2x80x9cunicastxe2x80x9d addresses, are static. On the other hand, the multicast addresses may be dynamic as respective multicast groups are formed and later dissolved.
Typically, a large-scale network such as a xe2x80x9cwide area networkxe2x80x9d (xe2x80x9cWANxe2x80x9d) is organized into a number of regions, each including a number of devices and router nodes and other components. Generally, one of the router nodes in each region will effectively be used as an interface to the other regions so that, if a source device in one region wishes to send a message packet to a destination device in another region, it (that is, the source device) will transmit the message packet to the inter-region router node. The inter-region router node in the source device""s region will, in turn, transfer the message packet to the inter-region router node in the destination device""s region, and the inter-region router node in the destination device""s region will forward the message packet in that region to the destination device.
Each of the inter-region router nodes makes use of routing information to identify the addresses for which each of the other inter-region router nodes is responsible, that is, the addresses for which it (the respective inter-region router node) is to transmit message packets which contain those addresses as destination addresses. In a large network, that is, a network including a large number of devices, such routing information may get to be correspondingly large, and would require a large amount of memory for each inter-region router node to store information for each address. Accordingly, it is generally desirable to store the address information as a range or ranges of addresses. However, it is typically difficult to determine address ranges which are appropriate for each router node to associate with other inter-region router nodes. This problem is exacerbated since the address ranges for which the respective inter-region router nodes re responsible, or with which they may be otherwise associated, may be relatively sparsely populated and may overlap with address ranges for other inter-region router nodes. In addition, the appropriate ranges may change if, for example, a device, router node or other component requiring an address is added to a network, or if unicast or multicast addresses are assigned on a dynamic basis, if routing policies change, or for other reasons which will be appreciated by those skilled in the art.
The invention provides a new and improved system and method for facilitating determination by router nodes in a network, particularly inter-region router nodes, of ranges of addresses for which each router node is responsible.
In brief summary, the invention provides a network including routers which route message packets among devices, thereby to facilitate transfer of information thereamong. Each router node makes use of routing information that identifies, inter alia, addresses and address ranges for which it is responsible, that the respective router node uses in routing a message packet that it receives. Each router node, through a negotiation operation with other router nodes, attempts to aggregate addresses for which it is responsible into one or more address ranges which do not overlap with addresses for which the other router nodes are responsible, and provides the address range(s), along with addresses for which it is responsible which could not be so aggregated, to the other router nodes for use as their routing information.
Since each router node determines its respective address ranges through negotiations with other router nodes, router nodes can be readily be added to the network without requiring, for example, a network administrator to manually adjust the routing information for each of the other router nodes. In addition, addresses can be easily assigned on a dynamic basis, since the router nodes can easily determine appropriate address ranges to provide to other router nodes for use in connection with their routing information.